<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html><head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="robots" content="index,nofollow">

<title>OsTrain2009/O1 - OS Teaching Wiki</title>
<script type="text/javascript" src="O1_files/common.js"></script>

<script type="text/javascript">
<!--// common functions

// We keep here the state of the search box
searchIsDisabled = false;

function searchChange(e) {
    // Update search buttons status according to search box content.
    // Ignore empty or whitespace search term.
    var value = e.value.replace(/\s+/, '');
    if (value == '' || searchIsDisabled) { 
        searchSetDisabled(true);
    } else {
        searchSetDisabled(false);
    }
}

function searchSetDisabled(flag) {
    // Enable or disable search
    document.getElementById('fullsearch').disabled = flag;
    document.getElementById('titlesearch').disabled = flag;
}

function searchFocus(e) {
    // Update search input content on focus
    if (e.value == 'Search') {
        e.value = '';
        e.className = '';
        searchIsDisabled = false;
    }
}

function searchBlur(e) {
    // Update search input content on blur
    if (e.value == '') {
        e.value = 'Search';
        e.className = 'disabled';
        searchIsDisabled = true;
    }
}

function actionsMenuInit(title) {
    // Initialize action menu
    for (i = 0; i < document.forms.length; i++) {
        var form = document.forms[i];
        if (form.className == 'actionsmenu') {
            // Check if this form needs update
            var div = form.getElementsByTagName('div')[0];
            var label = div.getElementsByTagName('label')[0];
            if (label) {
                // This is the first time: remove label and do buton.
                div.removeChild(label);
                var dobutton = div.getElementsByTagName('input')[0];
                div.removeChild(dobutton);
                // and add menu title
                var select = div.getElementsByTagName('select')[0];
                var item = document.createElement('option');
                item.appendChild(document.createTextNode(title));
                item.value = 'show';
                select.insertBefore(item, select.options[0]);
                select.selectedIndex = 0;
            }
        }
    }
}
//-->
</script>

<script type="text/javascript">
var gui_editor_link_href = "/oscourse/OsTrain2009/O1?action=edit&editor=gui";
var gui_editor_link_text = "Edit (GUI)";
</script>        

<link rel="stylesheet" type="text/css" charset="utf-8" media="all" href="O1_files/common.css">
<link rel="stylesheet" type="text/css" charset="utf-8" media="screen" href="O1_files/screen.css">
<link rel="stylesheet" type="text/css" charset="utf-8" media="print" href="O1_files/print.css">
<link rel="stylesheet" type="text/css" charset="utf-8" media="projection" href="O1_files/projection.css">

<!-- css only for MSIE browsers -->
<!--[if IE]>
   <link rel="stylesheet" type="text/css" charset="utf-8" media="all" href="/moin_static160/modern/css/msie.css">
<![endif]-->



<link rel="Start" href="http://os.cs.tsinghua.edu.cn/oscourse/FrontPage">
<link rel="Alternate" title="Wiki Markup" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=raw">
<link rel="Alternate" media="print" title="Print View" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=print">
<link rel="Up" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009">
<link rel="Appendix" title="2010处理机调度算法O1_by_wangemng.pptx" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=view&amp;target=2010%E5%A4%84%E7%90%86%E6%9C%BA%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95O1_by_wangemng.pptx">
<link rel="Appendix" title="2010处理机调度算法O1_by_wangmeng.pdf" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=view&amp;target=2010%E5%A4%84%E7%90%86%E6%9C%BA%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95O1_by_wangmeng.pdf">
<link rel="Appendix" title="2010处理机调度算法O1_实验设计.pdf" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=view&amp;target=2010%E5%A4%84%E7%90%86%E6%9C%BA%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95O1_%E5%AE%9E%E9%AA%8C%E8%AE%BE%E8%AE%A1.pdf">
<link rel="Appendix" title="2010处理机调度算法O1_实验设计.pptx" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=view&amp;target=2010%E5%A4%84%E7%90%86%E6%9C%BA%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95O1_%E5%AE%9E%E9%AA%8C%E8%AE%BE%E8%AE%A1.pptx">
<link rel="Appendix" title="2010处理机调度算法O1实验报告.pdf" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=view&amp;target=2010%E5%A4%84%E7%90%86%E6%9C%BA%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95O1%E5%AE%9E%E9%AA%8C%E6%8A%A5%E5%91%8A.pdf">
<link rel="Appendix" title="LinuxO(1)算法剖析" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=view&amp;target=LinuxO%281%29%E7%AE%97%E6%B3%95%E5%89%96%E6%9E%90">
<link rel="Appendix" title="Linux进程调度分析.pdf" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=view&amp;target=Linux%E8%BF%9B%E7%A8%8B%E8%B0%83%E5%BA%A6%E5%88%86%E6%9E%90.pdf">
<link rel="Appendix" title="proj_backup.tar.gz" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=view&amp;target=proj_backup.tar.gz">
<link rel="Appendix" title="处理器O(1)调度算法.ppt" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=view&amp;target=%E5%A4%84%E7%90%86%E5%99%A8O%281%29%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95.ppt">
<link rel="Appendix" title="处理机调度算法O1实验报告.docx" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=view&amp;target=%E5%A4%84%E7%90%86%E6%9C%BA%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95O1%E5%AE%9E%E9%AA%8C%E6%8A%A5%E5%91%8A.docx">
<link rel="Search" href="http://os.cs.tsinghua.edu.cn/oscourse/FindPage">
<link rel="Index" href="http://os.cs.tsinghua.edu.cn/oscourse/TitleIndex">
<link rel="Glossary" href="http://os.cs.tsinghua.edu.cn/oscourse/WordIndex">
<link rel="Help" href="http://os.cs.tsinghua.edu.cn/oscourse/HelpOnFormatting">
</head>

<body dir="ltr" lang="en">

<div id="header">
<div id="logo"><a href="http://os.cs.tsinghua.edu.cn/oscourse/FrontPage"><img src="O1_files/tsinghua63x64.gif" alt="OS Teaching"></a></div>

<form id="searchform" method="get" action="">
<div>
<input name="action" value="fullsearch" type="hidden">
<input name="context" value="180" type="hidden">
<label style="display: none;" for="searchinput">Search:</label>
<input class="disabled" id="searchinput" name="value" value="Search" size="20" onfocus="searchFocus(this)" onblur="searchBlur(this)" onkeyup="searchChange(this)" onchange="searchChange(this)" alt="Search" type="text">
<input disabled="disabled" id="titlesearch" name="titlesearch" value="Titles" alt="Search Titles" type="submit">
<input disabled="disabled" id="fullsearch" name="fullsearch" value="Text" alt="Search Full Text" type="submit">
</div>
</form>
<script type="text/javascript">
<!--// Initialize search form
var f = document.getElementById('searchform');
f.getElementsByTagName('label')[0].style.display = 'none';
var e = document.getElementById('searchinput');
searchChange(e);
searchBlur(e);
//-->
</script>

<ul id="username"><li><a class="nonexistent" href="http://os.cs.tsinghua.edu.cn/oscourse/2008010486" id="userhome" title="2008010486 @ Self">2008010486</a></li><li><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=userprefs" id="userprefs">Preferences</a></li><li><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=logout&amp;logout=logout" id="logout">Logout</a></li></ul>
<div id="locationline">
<div id="interwiki"><span><a href="http://os.cs.tsinghua.edu.cn/oscourse/FrontPage">OsCourseWiki</a></span></div>

<ul id="pagelocation">
<li><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009">OsTrain2009</a></li><li><a class="backlink" title="Click to do a full-text search for this title" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=fullsearch&amp;value=linkto%3A%22OsTrain2009/O1%22&amp;context=180">O1</a></li>
</ul>

</div>

<ul id="pagetrail">
<li><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2011/test/shell">OsTrain2011/test/shell</a></li><li><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2011/porting/MultiPlatform">MultiPlatform</a></li><li><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2011">OsTrain2011</a></li><li><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2011/porting">OsTrain2011/porting</a></li><li><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1">OsTrain2009/O1</a></li>
</ul>

<ul id="navibar">
<li class="wikilink"><a href="http://os.cs.tsinghua.edu.cn/oscourse/RecentChanges">RecentChanges</a></li><li class="wikilink"><a href="http://os.cs.tsinghua.edu.cn/oscourse/FindPage">FindPage</a></li><li class="wikilink"><a href="http://os.cs.tsinghua.edu.cn/oscourse/HelpContents">HelpContents</a></li><li class="current"><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1">OsTrain2009/O1</a></li>
</ul>

<div id="pageline"><hr style="display:none;"></div>

<ul class="editbar"><li><a name="texteditlink" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=edit&amp;editor=text">Edit (Text)</a></li><li><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=edit&amp;editor=gui">Edit (GUI)</a></li><li><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=info">Info</a></li><li><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=subscribe">Subscribe</a></li><li><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=quicklink">Add Link</a></li><li><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile">Attachments</a></li><li>
<form class="actionsmenu" method="get" action="">
<div>
    
    <select name="action" onchange="if ((this.selectedIndex != 0) &amp;&amp;
                      (this.options[this.selectedIndex].disabled == false)) {
                this.form.submit();
            }
            this.selectedIndex = 0;">
        <option selected="selected" value="show">More Actions:</option><option value="raw">Raw Text</option>
<option value="print">Print View</option>
<option value="RenderAsDocbook">Render as Docbook</option>
<option value="refresh">Delete Cache</option>
<option value="show" disabled="disabled" class="disabled">------------</option>
<option value="SpellCheck">Check Spelling</option>
<option value="LikePages">Like Pages</option>
<option value="LocalSiteMap">Local Site Map</option>
<option value="show" disabled="disabled" class="disabled">------------</option>
<option value="RenamePage" disabled="disabled" class="disabled">Rename Page</option>
<option value="DeletePage" disabled="disabled" class="disabled">Delete Page</option>
<option value="show" disabled="disabled" class="disabled">------------</option>
<option value="MyPages">My Pages</option>
<option value="SubscribeUser">Subscribe User</option>
<option value="show" disabled="disabled" class="disabled">------------</option>
<option value="Despam">Remove Spam</option>
<option value="PackagePages">Package Pages</option>
    </select>
    
</div>
<script type="text/javascript">
<!--// Init menu
actionsMenuInit('More Actions:');
//-->
</script>
</form>
</li></ul>

</div>

<div id="page" dir="ltr" lang="zh">
<div dir="ltr" id="content" lang="zh"><span class="anchor" id="top"></span>
<span class="anchor" id="line-8"></span><p class="line867">
</p><h1 id="head-c5233f0de6c8c517e98677ba82a344c687e60921">专题训练大实验-调度算法O1移植 2010</h1>
<span class="anchor" id="line-9"></span><p class="line867"></p><hr><p class="line874"> <span class="anchor" id="line-10"></span></p><ul><li style="list-style-type:none"><div class="table-of-contents"><p class="table-of-contents-heading">Contents</p><ol><li><a href="#head-c5233f0de6c8c517e98677ba82a344c687e60921">专题训练大实验-调度算法O1移植 2010</a><ol><li><a href="#head-8d77df4641182e8dcbdcee0b5cb530345e649510">小组成员</a></li><li><a href="#head-009aceeb7c3cb73efe80b680672662cd420ee166">实验任务描述</a></li><li><a href="#head-6bc7c95e57382aefe5fe37a4a9c23a650d6406f6">已有工作</a></li><li><a href="#head-6d07a05c22cee29cdb6acd2e85b020c2e47aaacf">实验分工</a></li><li><a href="#head-fd8af1432b1c1b832048b361be687fcb75432f3c">实验日志</a><ol><li><a href="#head-f73360f0bb078ad9cb036dcb6b719dae63fc7a1b">20101225</a></li><li><a href="#head-a71642766a988a42ab39954d28a96cf749789421">201012</a></li></ol></li><li><a href="#head-6417111caddf9a1eeede075dca71f75907541fad">实验报告</a><ol><li><a href="#head-3549059281d7e24bf7f82fe225c5938760080c83">Linux 中的 O(1) 调度器</a></li><li><a href="#head-5b778bbaf295e33711afbb1fdbe4957b8166d03e">O(1) 调度器的数据结构</a></li><li><a href="#head-7fb3a7e4bac56b9e3d9082887e9e7066980aa7df">xv6 中 O(1) 调度器的设计与实现</a></li><li><a href="#head-f4efa81c11363a6a8dba0849058f5eddcf898d7c">存在的问题和建议</a></li></ol></li></ol></li><li><a href="#head-a364644f2bbe5366343795d0bf57a67cb9d1ac3a">专题训练大实验-调度算法O1移植 2009</a><ol><li><a href="#head-009aceeb7c3cb73efe80b680672662cd420ee166-2">实验任务描述</a></li><li><a href="#head-d65ef0d533b0b104c093f206a312e183b401be3d">实验过程</a></li><li><a href="#head-df9e88bf278a6d18de4f63006ddd24338944c792">O(1)调度算法基本思想</a></li><li><a href="#head-37933ad9480c346544e5c21b98f246015f4b02d8">O(1)调度算法实现的简单介绍</a></li><li><a href="#head-e8f4888ed8544c43fe8596336cd8eb84eaf06c49">O(1)调度器小节</a></li><li><a href="#head-05265ed56aed2991e21d7029631866ee06e86917">代码描述</a></li><li><a href="#head-557be94e9091139a6e7c472c60877d00a133b793">实验总结</a><ol><li><a href="#head-73f1d8f798d96769dc51794fbb43c45f565661c6">20100123-张宇龙提交的O(1)算法代码</a></li></ol></li><li><a href="#head-30da62ccf277ba12c1f8abd0b21709aed1a7fe53">参考文献</a></li><li><a href="#head-c474f93037e115b55b4b5656071eb8dcc4e1caca">课堂讨论ppt</a></li></ol></li></ol></div> 在这里维护2010年秋操作系统专题训练课的大实验进行情况。请各位同学在上传自己的工作后在“日志”中按时间的逆序加入一条记录，简要说明所完成的工作。 <span class="anchor" id="line-11"></span><span class="anchor" id="line-12"></span></li></ul><p class="line867">
</p><h2 id="head-8d77df4641182e8dcbdcee0b5cb530345e649510">小组成员</h2>
<span class="anchor" id="line-13"></span><p class="line874">2007011406 薛超 <span class="anchor" id="line-14"></span><span class="anchor" id="line-15"></span></p><p class="line874">2007011410 王濛 <span class="anchor" id="line-16"></span><span class="anchor" id="line-17"></span></p><p class="line867">
</p><h2 id="head-009aceeb7c3cb73efe80b680672662cd420ee166">实验任务描述</h2>
<span class="anchor" id="line-18"></span><p class="line874">将 Linux 2.6 内核中出现的 O(1) 调度器移植到 xv6 中，并测试其正确性。 <span class="anchor" id="line-19"></span><span class="anchor" id="line-20"></span></p><p class="line867">
</p><h2 id="head-6bc7c95e57382aefe5fe37a4a9c23a650d6406f6">已有工作</h2>
<span class="anchor" id="line-21"></span><p class="line874">我们发现在 2009 
年的操作系统训练课程中已有同学在这方面做了一定的工作，但经过考察研究他们的实验结果，发现他们的代码还存在很多语法错误，在改正完语法错误后，代码可
以编译，但是系统无法正常进行调度，这表明他们的代码中还存在一定的逻辑错误。经过讨论，我们决定自己重新在 xv6 的调度框架下实现一个新的  
O(1) 调度器。 <span class="anchor" id="line-22"></span><span class="anchor" id="line-23"></span></p><p class="line867">
</p><h2 id="head-6d07a05c22cee29cdb6acd2e85b020c2e47aaacf">实验分工</h2>
<span class="anchor" id="line-24"></span><p class="line874">查找资料（共同） <span class="anchor" id="line-25"></span><span class="anchor" id="line-26"></span></p><p class="line874">熟悉O(1)算法（共同） <span class="anchor" id="line-27"></span><span class="anchor" id="line-28"></span></p><p class="line874">研究09年资料，并尝试修改（王濛为主） <span class="anchor" id="line-29"></span><span class="anchor" id="line-30"></span></p><p class="line874">理清思路，以 RR 为基础重新编写代码（薛超为主） <span class="anchor" id="line-31"></span><span class="anchor" id="line-32"></span></p><p class="line874">报告撰写（王濛，薛超） <span class="anchor" id="line-33"></span><span class="anchor" id="line-34"></span></p><p class="line867">
</p><h2 id="head-fd8af1432b1c1b832048b361be687fcb75432f3c">实验日志</h2>
<span class="anchor" id="line-35"></span><p class="line867">
</p><h3 id="head-f73360f0bb078ad9cb036dcb6b719dae63fc7a1b">20101225</h3>
<span class="anchor" id="line-36"></span><p class="line874">实验展示，展示文档如下： <span class="anchor" id="line-37"></span><span class="anchor" id="line-38"></span></p><p class="line867"><a class="attachment" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=get&amp;target=2010%E5%A4%84%E7%90%86%E6%9C%BA%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95O1_by_wangemng.pptx" title="attachment:2010处理机调度算法O1_by_wangemng.pptx">2010处理机调度算法O1_by_wangemng.pptx</a> <span class="anchor" id="line-39"></span><span class="anchor" id="line-40"></span></p><p class="line867"><a class="attachment" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=get&amp;target=2010%E5%A4%84%E7%90%86%E6%9C%BA%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95O1_by_wangmeng.pdf" title="attachment:2010处理机调度算法O1_by_wangmeng.pdf">2010处理机调度算法O1_by_wangmeng.pdf</a> <span class="anchor" id="line-41"></span><span class="anchor" id="line-42"></span></p><p class="line867">
</p><h3 id="head-a71642766a988a42ab39954d28a96cf749789421">201012</h3>
<span class="anchor" id="line-43"></span><p class="line874">实验方案设计展示文档： <span class="anchor" id="line-44"></span><span class="anchor" id="line-45"></span></p><p class="line867"><a class="attachment" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=get&amp;target=2010%E5%A4%84%E7%90%86%E6%9C%BA%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95O1_%E5%AE%9E%E9%AA%8C%E8%AE%BE%E8%AE%A1.pdf" title="attachment:2010处理机调度算法O1_实验设计.pdf">2010处理机调度算法O1_实验设计.pdf</a> <span class="anchor" id="line-46"></span><span class="anchor" id="line-47"></span></p><p class="line867"><a class="attachment" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=get&amp;target=2010%E5%A4%84%E7%90%86%E6%9C%BA%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95O1_%E5%AE%9E%E9%AA%8C%E8%AE%BE%E8%AE%A1.pptx" title="attachment:2010处理机调度算法O1_实验设计.pptx">2010处理机调度算法O1_实验设计.pptx</a> <span class="anchor" id="line-48"></span><span class="anchor" id="line-49"></span><span class="anchor" id="line-50"></span></p><p class="line867">
</p><h2 id="head-6417111caddf9a1eeede075dca71f75907541fad">实验报告</h2>
<span class="anchor" id="line-51"></span><p class="line874">实验报告文档： <span class="anchor" id="line-52"></span><span class="anchor" id="line-53"></span></p><p class="line867"><a class="attachment" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=get&amp;target=2010%E5%A4%84%E7%90%86%E6%9C%BA%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95O1%E5%AE%9E%E9%AA%8C%E6%8A%A5%E5%91%8A.pdf" title="attachment:2010处理机调度算法O1实验报告.pdf">2010处理机调度算法O1实验报告.pdf</a> <span class="anchor" id="line-54"></span><span class="anchor" id="line-55"></span></p><p class="line867"><a class="attachment" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=get&amp;target=%E5%A4%84%E7%90%86%E6%9C%BA%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95O1%E5%AE%9E%E9%AA%8C%E6%8A%A5%E5%91%8A.docx" title="attachment:处理机调度算法O1实验报告.docx">处理机调度算法O1实验报告.docx</a> <span class="anchor" id="line-56"></span><span class="anchor" id="line-57"></span><span class="anchor" id="line-58"></span></p><p class="line867">
</p><h3 id="head-3549059281d7e24bf7f82fe225c5938760080c83">Linux 中的 O(1) 调度器</h3>
<span class="anchor" id="line-59"></span><p class="line874">Linux 2.4 
的调度器对数目不断增加的处理器和进程的情况扩展得不是很好，为了解决这个问题，Linux 2.6 使用了一个全新的调度器（称为 O(1) 
调度器）。这个调度器能够保证无论系统的负载或者处理器的数目如何，选择合适的进程并且给它分配处理器的时间是固定的。 <span class="anchor" id="line-60"></span><span class="anchor" id="line-61"></span></p><p class="line874">a)      Linux 2.4 中的调度器 <span class="anchor" id="line-62"></span><span class="anchor" id="line-63"></span></p><p class="line874">对runqueue中的所有进程比较优先级，选出最高优先级进行调度。 <span class="anchor" id="line-64"></span><span class="anchor" id="line-65"></span></p><p class="line874">i.      普通进程 <span class="anchor" id="line-66"></span><span class="anchor" id="line-67"></span></p><p class="line874">时间片：随时钟中断递减，用完待分配 <span class="anchor" id="line-68"></span><span class="anchor" id="line-69"></span></p><p class="line874">优先级：进程中Counter决定，加上原来的Counter(xv6:timeslice) <span class="anchor" id="line-70"></span><span class="anchor" id="line-71"></span></p><p class="line874">ii.     实时进程 <span class="anchor" id="line-72"></span><span class="anchor" id="line-73"></span></p><p class="line874">优先级由静态设定，高于普通进程 <span class="anchor" id="line-74"></span><span class="anchor" id="line-75"></span></p><p class="line874">时间片用完，重新分配插入runqueue <span class="anchor" id="line-76"></span><span class="anchor" id="line-77"></span></p><p class="line874">调度策略: FIFO，RR <span class="anchor" id="line-78"></span><span class="anchor" id="line-79"></span></p><p class="line874">iii.    问题 <span class="anchor" id="line-80"></span><span class="anchor" id="line-81"></span></p><p class="line874">O(n)，遍历 runqueue <span class="anchor" id="line-82"></span><span class="anchor" id="line-83"></span></p><p class="line874">SMP，使用一个 runqueue <span class="anchor" id="line-84"></span><span class="anchor" id="line-85"></span></p><p class="line874">实时性，不支持抢占 <span class="anchor" id="line-86"></span><span class="anchor" id="line-87"></span></p><p class="line874">对于处理器数目不断增加、实时任务需求变大的情况无法很好适应 <span class="anchor" id="line-88"></span><span class="anchor" id="line-89"></span></p><p class="line874">b)      O(1)调度器的特点 <span class="anchor" id="line-90"></span><span class="anchor" id="line-91"></span></p><p class="line874">i.      支持动态抢占，从优先级区分实时任务和非实时任务。同一优先级内采用 FIFO 或 RR 进行调度。 <span class="anchor" id="line-92"></span><span class="anchor" id="line-93"></span></p><p class="line874">实时任务：0 – 99 <span class="anchor" id="line-94"></span><span class="anchor" id="line-95"></span></p><p class="line874">非实时任务：100 - 139 <span class="anchor" id="line-96"></span><span class="anchor" id="line-97"></span></p><p class="line874">ii.     支持负载均衡 <span class="anchor" id="line-98"></span><span class="anchor" id="line-99"></span></p><p class="line874">iii.    支持恒定速度进行调度， O(1) <span class="anchor" id="line-100"></span><span class="anchor" id="line-101"></span></p><p class="line867">
</p><h3 id="head-5b778bbaf295e33711afbb1fdbe4957b8166d03e">O(1) 调度器的数据结构</h3>
<span class="anchor" id="line-102"></span><p class="line874">在系统中，内核为每个处理器维持了两个调度的数据结构，形式如下： <span class="anchor" id="line-103"></span><span class="anchor" id="line-104"></span></p><p class="line874">struct  prio_array { <span class="anchor" id="line-105"></span></p><ul><li style="list-style-type:none">int                     nr_active;                              // 数组中的任务数 <span class="anchor" id="line-106"></span>unsigned long           bitmap[BITMAP_SIZe];            // 优先级位图 <span class="anchor" id="line-107"></span>struct list_head        queue[MAX_PRIO];                        // 优先级队列 <span class="anchor" id="line-108"></span></li></ul><p class="line874">} <span class="anchor" id="line-109"></span><span class="anchor" id="line-110"></span></p><p class="line874">Linux
 为每个优先级级别维护了一个单独的队列。总的队列个数是 MAX_PRIO，默认值是 
140。这个结构同样包含了一个有足够大小的位图数组来为每一个优先级级别提供一个比特。因此，BITMAP_SIZE 的值为 5，这就创建了有 
160 个比特位的位图，其中 20 个被忽略掉。位图指示了哪些队列是空的。最后，nr_active 
指示了在所有队列上的总任务的个数。这两个结构被维护为一个活动队列结构和一个过期的队列结构。 <span class="anchor" id="line-111"></span><span class="anchor" id="line-112"></span></p><p class="line874">为了适应上述变化，需要在 runqueue 中添加新的参数，如下： <span class="anchor" id="line-113"></span><span class="anchor" id="line-114"></span></p><p class="line874">struct  rq { <span class="anchor" id="line-115"></span></p><ul><li style="list-style-type:none">. . <span class="anchor" id="line-116"></span>struct  prio_array*     active;         // 活动队列指针 <span class="anchor" id="line-117"></span>struct  prio_array*     expired;                // 过期队列指针 <span class="anchor" id="line-118"></span>struct  prio_array      arrays[2];              // 实际队列 <span class="anchor" id="line-119"></span></li><li style="list-style-type:none">. . <span class="anchor" id="line-120"></span></li></ul><p class="line874">} <span class="anchor" id="line-121"></span><span class="anchor" id="line-122"></span></p><p class="line874">活动队列和过期队列的指针的组织结构如下图： <span class="anchor" id="line-123"></span><span class="anchor" id="line-124"></span><span class="anchor" id="line-125"></span></p><p class="line874">O(1) 调度器的调度结构如下图： <span class="anchor" id="line-126"></span><span class="anchor" id="line-127"></span></p><p class="line874">调度器从活动队列中选取将要执行的进程，在条件满足时（非实时任务，时间片用完），将进程从活动进程数组移动到过期进程数组中，并更新该进程的优先级和时间片等信息。当活动数组为空时，则交换 active 和 expired 指针。具体的调度过程如下图所示： <span class="anchor" id="line-128"></span><span class="anchor" id="line-129"></span><span class="anchor" id="line-130"></span></p><p class="line874">初
始化的时候，位图都被设置为 0 
并且所有的队列都为空，当一个进程就绪的时候，将它放到合适的优先级队列，队列具有活动队列结构并且被赋予了合适的时间片。如果一个任务在它完成它的时间
片之前被抢占，则它将返回到活动队列。当任务完成了它的时间片后，则它将会进入合适的过期队列并被赋予新的时间片。所有的调度都发生在处在活动队列结构的
任务中。当活动队列为空的时候，一个简单的指针赋值操作将导致活动队列和过期队列之间的转换，并且调度继续进行。 <span class="anchor" id="line-131"></span><span class="anchor" id="line-132"></span></p><p class="line874">对一个给定的处理器，调度器选择具有最高优先级的非空队列，如果队列中有多个任务，任务将会以轮转方式进行调度。 <span class="anchor" id="line-133"></span><span class="anchor" id="line-134"></span></p><p class="line874">在 PCB 中需要添加优先级域以适应 O(1) 调度器，添加的项如下： <span class="anchor" id="line-135"></span><span class="anchor" id="line-136"></span></p><p class="line874">struc   proc { <span class="anchor" id="line-137"></span></p><ul><li style="list-style-type:none">. . <span class="anchor" id="line-138"></span>int     prio;                                           // 动态优先级 <span class="anchor" id="line-139"></span>int static_prio;                                        // 静态优先级 <span class="anchor" id="line-140"></span>unsigned long sleep_avg;                // 平均睡眠时间 <span class="anchor" id="line-141"></span></li><li style="list-style-type:none">. . <span class="anchor" id="line-142"></span><span class="anchor" id="line-143"></span></li></ul><p class="line874">} <span class="anchor" id="line-144"></span><span class="anchor" id="line-145"></span></p><p class="line874">在
 Linux 2.6 中，静态优先级 
static_prio在进程创建的时候就被赋值，并且不变（除非用系统调用改变进程），动态优先级prio则是跟static_prio和
sleep_avg有关。实时进程的优先级在创建的时候就确定了，而且一旦确定以后就不再改变，其范围为 0 ~ 
99；非实时进程的优先级根据静态优先级和 sleep_avg计算获得，其范围为 100 ~ 139。 <span class="anchor" id="line-146"></span><span class="anchor" id="line-147"></span></p><p class="line874">优先级的计算或更新会发生在下列事件发生时： <span class="anchor" id="line-148"></span><span class="anchor" id="line-149"></span></p><p class="line874">a)      创建新进程，此时进程尚未进行调度，直接给出优先级的值； <span class="anchor" id="line-150"></span><span class="anchor" id="line-151"></span></p><p class="line874">b)      唤醒等待进程，此时需要计算进程的动态优先级； <span class="anchor" id="line-152"></span><span class="anchor" id="line-153"></span></p><p class="line874">c)      进程用完时间片以后，被重新插入到active array或者expired array的时候需要重新计算动态优先级，以便将进程插入到队列的相应位置； <span class="anchor" id="line-154"></span><span class="anchor" id="line-155"></span></p><p class="line874">d)       其他情况，如IDLE进程初始化等时候。 <span class="anchor" id="line-156"></span><span class="anchor" id="line-157"></span></p><p class="line874">对
于 Linux 2.6 中的时间片，time_slice 
是基于静态优先级的，静态优先级越高（值越小），时间片就越大，使用线性映射的方法将进程优先级 [MAX_RT_PRIO, MAX_PRIO-1] 
映射到时间片 [MIN_TIMESLICE,  MAX_TIMESLICE] 范围内。 <span class="anchor" id="line-158"></span><span class="anchor" id="line-159"></span></p><p class="line874">在旧版本的 Linux 系统中会使用下面的循环来给进程队列计算时间片： <span class="anchor" id="line-160"></span><span class="anchor" id="line-161"></span></p><p class="line874">for (each task on the system) { <span class="anchor" id="line-162"></span><span class="anchor" id="line-163"></span></p><ul><li style="list-style-type:none">recalculate priority; <span class="anchor" id="line-164"></span><span class="anchor" id="line-165"></span>recalculate timeslice <span class="anchor" id="line-166"></span><span class="anchor" id="line-167"></span></li></ul><p class="line874">} <span class="anchor" id="line-168"></span><span class="anchor" id="line-169"></span></p><p class="line874">这
种方式存在很大的不足，循环可能会花很长时间，而且算法的复杂度为 O(n)，当 n 变大时这种花费会变得无法容忍；计算过程中必须要给进程队列和 
task_struct 上锁，这样可能导致大量的竞争；计算的时间不可预计，可能给实时进程带来问题。在 Linux 2.6 
中时间片是分散计算的，时间片的计算会发生在下列事件发生时： <span class="anchor" id="line-170"></span><span class="anchor" id="line-171"></span></p><p class="line874">a)      进程创建时，将父进程的时间片分一半给子进程，同时父进程的时间片减半； <span class="anchor" id="line-172"></span><span class="anchor" id="line-173"></span></p><p class="line874">b)      进程用完时间片以后，需要重新计算时间片，并将进程插入到相应的运行队列； <span class="anchor" id="line-174"></span><span class="anchor" id="line-175"></span></p><p class="line874">c)      进程退出时，根据first_timeslice的值来决定是否将子进程的时间片返还给父进程。 <span class="anchor" id="line-176"></span><span class="anchor" id="line-177"></span><span class="anchor" id="line-178"></span><span class="anchor" id="line-179"></span></p><p class="line867">
</p><h3 id="head-7fb3a7e4bac56b9e3d9082887e9e7066980aa7df">xv6 中 O(1) 调度器的设计与实现</h3>
<span class="anchor" id="line-180"></span><ul><li style="list-style-type:none">经过对 xv6 中已有调度算法 FIFO 和 RR 以及调度框架的研究，若将 O(1) 调度移植到 xv6 的调度框架内需要做如下的变动： <span class="anchor" id="line-181"></span><span class="anchor" id="line-182"></span></li></ul><p class="line874">a)      需要修改和添加的数据结构 <span class="anchor" id="line-183"></span><span class="anchor" id="line-184"></span></p><p class="line874">i.      struct proc {} <span class="anchor" id="line-185"></span><span class="anchor" id="line-186"></span></p><p class="line874">目录：include/process/proc.h <span class="anchor" id="line-187"></span><span class="anchor" id="line-188"></span></p><p class="line874">描述：在进程描述符 struct proc 内添加进程的优先级域，结构体内其他域不变。 <span class="anchor" id="line-189"></span><span class="anchor" id="line-190"></span></p><p class="line874">struct  proc { <span class="anchor" id="line-191"></span><span class="anchor" id="line-192"></span></p><ul><li style="list-style-type:none">. . <span class="anchor" id="line-193"></span><span class="anchor" id="line-194"></span>int     prio;                                           // 动态优先级 <span class="anchor" id="line-195"></span><span class="anchor" id="line-196"></span>int static_prio;                                        // 静态优先级 <span class="anchor" id="line-197"></span><span class="anchor" id="line-198"></span>unsigned long sleep_avg;                // 平均睡眠时间 <span class="anchor" id="line-199"></span><span class="anchor" id="line-200"></span></li><li class="gap" style="list-style-type:none">. . <span class="anchor" id="line-201"></span></li></ul><p class="line874">} <span class="anchor" id="line-202"></span><span class="anchor" id="line-203"></span></p><p class="line874">ii.     struct rq {} <span class="anchor" id="line-204"></span><span class="anchor" id="line-205"></span></p><p class="line874">目录：include/process/rq.h <span class="anchor" id="line-206"></span><span class="anchor" id="line-207"></span></p><p class="line874">描述：在 runqueue 结构体内添加处理器调度的数据结构域，其他域不变 <span class="anchor" id="line-208"></span><span class="anchor" id="line-209"></span></p><p class="line874">struct  rq { <span class="anchor" id="line-210"></span><span class="anchor" id="line-211"></span></p><ul><li style="list-style-type:none">. . <span class="anchor" id="line-212"></span><span class="anchor" id="line-213"></span>struct  prio_array*     active;         // 活动队列指针 <span class="anchor" id="line-214"></span><span class="anchor" id="line-215"></span>struct  prio_array*     expired;                // 过期队列指针 <span class="anchor" id="line-216"></span><span class="anchor" id="line-217"></span>struct  prio_array      arrays[2];              // 实际队列 <span class="anchor" id="line-218"></span><span class="anchor" id="line-219"></span></li><li class="gap" style="list-style-type:none">. . <span class="anchor" id="line-220"></span><span class="anchor" id="line-221"></span></li></ul><p class="line874">} <span class="anchor" id="line-222"></span><span class="anchor" id="line-223"></span></p><p class="line874">iii.    struct prio_array{} <span class="anchor" id="line-224"></span><span class="anchor" id="line-225"></span></p><p class="line874">目录：include/process/rq.h <span class="anchor" id="line-226"></span><span class="anchor" id="line-227"></span></p><p class="line874">描述：添加 O(1) 调度的数据结构，其他不变。 <span class="anchor" id="line-228"></span><span class="anchor" id="line-229"></span></p><p class="line874">struct  prio_array { <span class="anchor" id="line-230"></span><span class="anchor" id="line-231"></span></p><ul><li style="list-style-type:none">int                             nr_active;                              // 数组中的任务数 <span class="anchor" id="line-232"></span><span class="anchor" id="line-233"></span>unsigned long           bitmap[BITMAP_SIZe];            // 优先级位图 <span class="anchor" id="line-234"></span><span class="anchor" id="line-235"></span>struct rq_node* rq_O1[MAX_PRIO];                        // 优先级队列 <span class="anchor" id="line-236"></span><span class="anchor" id="line-237"></span></li></ul><p class="line874">} <span class="anchor" id="line-238"></span><span class="anchor" id="line-239"></span></p><p class="line874">b)      需要修改和添加的函数和文件 <span class="anchor" id="line-240"></span><span class="anchor" id="line-241"></span></p><p class="line874">i.      process/proc.c   <span class="anchor" id="line-242"></span><span class="anchor" id="line-243"></span></p><p class="line874">函数：pinit() <span class="anchor" id="line-244"></span><span class="anchor" id="line-245"></span></p><p class="line874">描述：根据 FIFO 和 RR，添加 O(1) 调度的注册信息. <span class="anchor" id="line-246"></span><span class="anchor" id="line-247"></span></p><p class="line874">// process/proc.c <span class="anchor" id="line-248"></span><span class="anchor" id="line-249"></span></p><p class="line874">. . . <span class="anchor" id="line-250"></span><span class="anchor" id="line-251"></span></p><p class="line874">#include “sched_O1.h” <span class="anchor" id="line-252"></span><span class="anchor" id="line-253"></span></p><p class="line874">. . . <span class="anchor" id="line-254"></span><span class="anchor" id="line-255"></span></p><p class="line874">#define SCHED_O1 <span class="anchor" id="line-256"></span><span class="anchor" id="line-257"></span></p><p class="line874">. . . <span class="anchor" id="line-258"></span><span class="anchor" id="line-259"></span></p><p class="line874">void pinit(void) <span class="anchor" id="line-260"></span><span class="anchor" id="line-261"></span></p><p class="line874">{ <span class="anchor" id="line-262"></span><span class="anchor" id="line-263"></span></p><ul><li style="list-style-type:none">. . <span class="anchor" id="line-264"></span><span class="anchor" id="line-265"></span></li></ul><p class="line874">#ifdef SCHED_O1 <span class="anchor" id="line-266"></span><span class="anchor" id="line-267"></span></p><ul><li style="list-style-type:none"><p class="line862">rq-&gt;sched_class = (struct sched_class *)&amp;sched_class_O1; <span class="anchor" id="line-268"></span><span class="anchor" id="line-269"></span></p><p class="line862">rq-&gt;sub_sched_class = (struct sched_class *)&amp;sched_class_O1; <span class="anchor" id="line-270"></span><span class="anchor" id="line-271"></span></p><p class="line862">rq-&gt;max_slices = 3; <span class="anchor" id="line-272"></span><span class="anchor" id="line-273"></span></p></li></ul><p class="line874">#endif <span class="anchor" id="line-274"></span><span class="anchor" id="line-275"></span></p><ul><li style="list-style-type:none">. . <span class="anchor" id="line-276"></span><span class="anchor" id="line-277"></span></li></ul><p class="line874">} <span class="anchor" id="line-278"></span><span class="anchor" id="line-279"></span></p><p class="line874">ii.     include/sched/ <span class="anchor" id="line-280"></span><span class="anchor" id="line-281"></span></p><p class="line874">文件：sched_O1.h <span class="anchor" id="line-282"></span><span class="anchor" id="line-283"></span></p><p class="line874">描述：根据FIFO 和 RR 的头文件，编写O(1) 头文件。 <span class="anchor" id="line-284"></span><span class="anchor" id="line-285"></span></p><p class="line874">// include/sched/sched_O1.h <span class="anchor" id="line-286"></span><span class="anchor" id="line-287"></span></p><p class="line862">#ifndef <span class="u">SCHED_O1_H <span class="anchor" id="line-288"></span><span class="anchor" id="line-289"></span></span></p><p class="line862">#define SCHED_O1_H <span class="anchor" id="line-290"></span><span class="anchor" id="line-291"></span></p><p class="line874">#include "rq.h" <span class="anchor" id="line-292"></span><span class="anchor" id="line-293"></span></p><p class="line874">extern const struct sched_class sched_class_O1; <span class="anchor" id="line-294"></span><span class="anchor" id="line-295"></span></p><p class="line874">#endif <span class="anchor" id="line-296"></span><span class="anchor" id="line-297"></span></p><p class="line874">iii.    sched/ <span class="anchor" id="line-298"></span><span class="anchor" id="line-299"></span></p><p class="line874">文件：sched_O1.c <span class="anchor" id="line-300"></span><span class="anchor" id="line-301"></span></p><p class="line874">描述：创建O(1) 源文件，实现调度所需函数。 <span class="anchor" id="line-302"></span><span class="anchor" id="line-303"></span></p><p class="line874">iv.     Makeflie <span class="anchor" id="line-304"></span><span class="anchor" id="line-305"></span></p><p class="line874">描述：将 sched_O1.o 添加到 OBJS/ <span class="anchor" id="line-306"></span><span class="anchor" id="line-307"></span></p><p class="line874">c)      实现的 O(1) 调度器的函数 <span class="anchor" id="line-308"></span><span class="anchor" id="line-309"></span></p><p class="line874">主要描述实现 O(1) 调度器所必须的几个函数。 <span class="anchor" id="line-310"></span><span class="anchor" id="line-311"></span></p><p class="line874">i.      sched_class 中的一系列函数 <span class="anchor" id="line-312"></span><span class="anchor" id="line-313"></span></p><p class="line874">描述：xv6 中调度框架所定义的一系列函数。 <span class="anchor" id="line-314"></span><span class="anchor" id="line-315"></span></p><p class="line874">ii.     bitmap 位操作 <span class="anchor" id="line-316"></span><span class="anchor" id="line-317"></span></p><p class="line874">1.      getBitmap() <span class="anchor" id="line-318"></span><span class="anchor" id="line-319"></span></p><p class="line874">int getBitmap(unsigned long bitmap[Bitmap_Size],int prio) <span class="anchor" id="line-320"></span><span class="anchor" id="line-321"></span></p><p class="line874">参数： <span class="anchor" id="line-322"></span><span class="anchor" id="line-323"></span></p><ul><li style="list-style-type:none">unsigned long bitmap[Bitmap_Size]：位图数组 <span class="anchor" id="line-324"></span><span class="anchor" id="line-325"></span>int prio：优先级 <span class="anchor" id="line-326"></span><span class="anchor" id="line-327"></span></li></ul><p class="line874">返回值： <span class="anchor" id="line-328"></span><span class="anchor" id="line-329"></span></p><p class="line874">0：该优先级所对应队列为空 <span class="anchor" id="line-330"></span><span class="anchor" id="line-331"></span></p><p class="line874">1：该优先级所对应队列不为空 <span class="anchor" id="line-332"></span><span class="anchor" id="line-333"></span></p><p class="line874">描述： <span class="anchor" id="line-334"></span><span class="anchor" id="line-335"></span></p><p class="line874">返回某一优先级所对应队列是否为空 <span class="anchor" id="line-336"></span><span class="anchor" id="line-337"></span></p><p class="line874">2.      modifyBitmap() <span class="anchor" id="line-338"></span><span class="anchor" id="line-339"></span></p><p class="line874">void modifyBitmap(unsigned long bitmap[Bitmap_Size],int prio,int reset) <span class="anchor" id="line-340"></span><span class="anchor" id="line-341"></span></p><p class="line874">参数： <span class="anchor" id="line-342"></span><span class="anchor" id="line-343"></span></p><ul><li style="list-style-type:none">unsigned long bitmap[Bitmap_Size]：位图数组； <span class="anchor" id="line-344"></span><span class="anchor" id="line-345"></span>int prio：优先级； <span class="anchor" id="line-346"></span><span class="anchor" id="line-347"></span>int reset：0，将位图某一位设为1；1，将位图某一位设为 0； <span class="anchor" id="line-348"></span><span class="anchor" id="line-349"></span></li></ul><p class="line874">返回值： <span class="anchor" id="line-350"></span><span class="anchor" id="line-351"></span></p><ul><li style="list-style-type:none">NULL <span class="anchor" id="line-352"></span><span class="anchor" id="line-353"></span></li></ul><p class="line874">描述： <span class="anchor" id="line-354"></span><span class="anchor" id="line-355"></span></p><ul><li style="list-style-type:none">设置某一优先级所对应队列的位图值。 <span class="anchor" id="line-356"></span><span class="anchor" id="line-357"></span></li></ul><p class="line874">3.      get_first_bitmap() <span class="anchor" id="line-358"></span><span class="anchor" id="line-359"></span></p><p class="line874">int get_first_bitmap(unsigned long bitmap[Bitmap_Size]) <span class="anchor" id="line-360"></span><span class="anchor" id="line-361"></span></p><p class="line874">参数： <span class="anchor" id="line-362"></span><span class="anchor" id="line-363"></span></p><ul><li style="list-style-type:none">unsigned long bitmap[Bitmap_Size]：位图数组； <span class="anchor" id="line-364"></span><span class="anchor" id="line-365"></span></li></ul><p class="line874">返回值： <span class="anchor" id="line-366"></span><span class="anchor" id="line-367"></span></p><ul><li style="list-style-type:none">位图中第一个不为 0 的位的 index <span class="anchor" id="line-368"></span><span class="anchor" id="line-369"></span></li></ul><p class="line874">描述： <span class="anchor" id="line-370"></span><span class="anchor" id="line-371"></span></p><ul><li style="list-style-type:none">查找位图中第一个不为0的位并返回该位的 index <span class="anchor" id="line-372"></span><span class="anchor" id="line-373"></span></li></ul><p class="line874">iii.    优先级计算与更改 <span class="anchor" id="line-374"></span><span class="anchor" id="line-375"></span></p><p class="line874">1.      现状：进程的优先级在进程enqueue时确定，并参考 Linux 2.6 内核中 O(1) 调度的实现提供了计算和更新优先级的接口。提供的接口简介如下： <span class="anchor" id="line-376"></span><span class="anchor" id="line-377"></span></p><p class="line874">void set_proc_prio_O1(struct proc *p,int prio,int static_prio) <span class="anchor" id="line-378"></span><span class="anchor" id="line-379"></span></p><p class="line874">描述：根据提供的参数设置进程 p 的优先级，其中参数 prio 和 static_prio 根据系统调用得到。 <span class="anchor" id="line-380"></span><span class="anchor" id="line-381"></span></p><p class="line874">void update_proc_prio_O1(struct proc *p) <span class="anchor" id="line-382"></span><span class="anchor" id="line-383"></span></p><p class="line874">描述：更新进程　p 的优先级。 <span class="anchor" id="line-384"></span><span class="anchor" id="line-385"></span></p><p class="line874">2.      改进：通过系统接口确定static_prio，并且在运行时维护 prio 和 timeslice(sleep_avg)。 <span class="anchor" id="line-386"></span><span class="anchor" id="line-387"></span><span class="anchor" id="line-388"></span></p><p class="line867">
</p><h3 id="head-f4efa81c11363a6a8dba0849058f5eddcf898d7c">存在的问题和建议</h3>
<span class="anchor" id="line-389"></span><p class="line874">a) 优先级的获得 <span class="anchor" id="line-390"></span><span class="anchor" id="line-391"></span></p><p class="line874">i. xv6 中没有既成优先级的接口，无法得到进程的初始优先级 <span class="anchor" id="line-392"></span><span class="anchor" id="line-393"></span></p><p class="line874">ii. xv6 中还没有区分实时和非实时进程 <span class="anchor" id="line-394"></span><span class="anchor" id="line-395"></span></p><p class="line874">b) 时间片分配的大小问题 <span class="anchor" id="line-396"></span><span class="anchor" id="line-397"></span></p><p class="line874">i. 在初始化时对所有的进程唯一确定 <span class="anchor" id="line-398"></span><span class="anchor" id="line-399"></span></p><p class="line874">ii. 最好提供一个时间片分配大小的评价函数，可以根据进程的优先级进行分配。 <span class="anchor" id="line-400"></span><span class="anchor" id="line-401"></span><span class="anchor" id="line-402"></span><span class="anchor" id="line-403"></span><span class="anchor" id="line-404"></span></p><p class="line867"></p><hr class="hr6"><p class="line874"> <span class="anchor" id="line-405"></span>
</p><h1 id="head-a364644f2bbe5366343795d0bf57a67cb9d1ac3a">专题训练大实验-调度算法O1移植 2009</h1>
<span class="anchor" id="line-406"></span><p class="line867">
</p><h2 id="head-009aceeb7c3cb73efe80b680672662cd420ee166-2">实验任务描述</h2>
<span class="anchor" id="line-407"></span><p class="line874">移植处理机调度算法O1至XV6系统，并测试其正确性； <span class="anchor" id="line-408"></span><span class="anchor" id="line-409"></span></p><p class="line874">小组成员: 张宇龙(2006012193) 凌瀛洲 (2006012206) 小组分工: 代码填写:凌瀛洲 实验报告撰写: 张宇龙 <span class="anchor" id="line-410"></span><span class="anchor" id="line-411"></span></p><p class="line867">
</p><h2 id="head-d65ef0d533b0b104c093f206a312e183b401be3d">实验过程</h2>
<span class="anchor" id="line-412"></span><p class="line874">12.2--12.7 选题并查阅参考资料和现有成果 12.17- 代码填写和实验报告 <span class="anchor" id="line-413"></span><span class="anchor" id="line-414"></span></p><p class="line867">
</p><h2 id="head-df9e88bf278a6d18de4f63006ddd24338944c792">O(1)调度算法基本思想</h2>
<span class="anchor" id="line-415"></span><p class="line874">不管系统中有多少可运行的进程，调度程序总能在一个恒定的时间内选择一个优先级最高的进程投入运行。 数据结构：runqueue 1、定义 struct  runqueue { <span class="anchor" id="line-416"></span><span class="anchor" id="line-417"></span></p><ul><li style="list-style-type:none">spinlock_t                      lock;                   //保护运行队列的自旋锁 <span class="anchor" id="line-418"></span></li></ul><p class="line874">unsinged long           nr_running;             //可运行进程数目 <span class="anchor" id="line-419"></span><span class="anchor" id="line-420"></span></p><ul><li style="list-style-type:none">…… <span class="anchor" id="line-421"></span></li></ul><p class="line874">struct prio_array               *active;                        //活动优先级队列 <span class="anchor" id="line-422"></span><span class="anchor" id="line-423"></span></p><ul><li style="list-style-type:none">struct prio_array               *expired;               //过期优先级队列 <span class="anchor" id="line-424"></span></li></ul><p class="line874">struct prio_array               arrays[2];              //实际优先级队列数组 …… }; 2图示 <span class="anchor" id="line-425"></span><span class="anchor" id="line-426"></span></p><p class="line874">Runqueue结构和可运行进程的两个集合 <span class="anchor" id="line-427"></span><span class="anchor" id="line-428"></span></p><p class="line874">优先级数组： struct prio_array { <span class="anchor" id="line-429"></span><span class="anchor" id="line-430"></span></p><ul><li style="list-style-type:none">int
                     nr_active;      //本队列中进程数目 unsigned long           
bitmap[BITMAP_SIZE];//优先级位图 struct list_head        
queue[MAX_PRIO];//每个优先级的进程链表 <span class="anchor" id="line-431"></span></li></ul><p class="line874">}; <span class="anchor" id="line-432"></span><span class="anchor" id="line-433"></span></p><p class="line867">
</p><h2 id="head-37933ad9480c346544e5c21b98f246015f4b02d8">O(1)调度算法实现的简单介绍</h2>
<span class="anchor" id="line-434"></span><p class="line874">(1)选择下一个优先级最高的进程来运行 <span class="anchor" id="line-435"></span><span class="anchor" id="line-436"></span></p><p class="line874">struct
  task_struct             *prev  *next;//指向进程描述符的指针 struct  list_head   
                    *queue;         //指向进程链头的指针 struct  prio_array      
                *array;         //指向优先级数组的指针 <span class="anchor" id="line-437"></span><span class="anchor" id="line-438"></span></p><p class="line862">prev
 = current;                         //把当前的进程描述符地址保存到prev array = 
rq-&gt;active;                     //用array指向活动优先级队列 idx = 
sched_find_first_bit(array-&gt;bitmap);//找到位图中第一个置1的位，//并把对应的优先级号赋给idx 
queue = array-&gt;queue + 
idx;//找到该优先级对应的活动队列数组元素地址，//该地址指向时间片还没用完的优先级为idx的进程链表 next = 
list_entry(queue-&gt;next, struct task_struct, run_list);//宏 
返回下一个应该投入运行的进程描述符的地址并赋给next <span class="anchor" id="line-439"></span><span class="anchor" id="line-440"></span></p><p class="line862">(2)
时间片的计算方法与时机 Linux2.4 调度系统在所有就绪进程的时间片都耗完以后在调度器中一次性重新计算,其中重算是用for循环相当耗时。 
for(系统中的每个任务){ 重新计算优先级 重新计算时间片 } 
Linux2.6为每个CPU保留active和expired两个优先级数组,active数组中包含了有剩余时间片的任务,expired数组中包含
了所有用完时间片的任务。 当一个任务的时间片用完了就会重新计算其时间片,并插入到 expired队列中,当active 队 
列中所有进程用完时间片时,只需交换指向active和expired队列的指针即可。此交换是实 现O(1)算法的核心,由 
schedule()中以下程序来实现: struct  prio_array              *array = 
rq-&gt;active; if(!array-&gt;nr_active){ <span class="anchor" id="line-441"></span><span class="anchor" id="line-442"></span></p><ul><li style="list-style-type:none"><p class="line862">rq-&gt;active = rq-&gt;expired; rq-&gt;expired = array; <span class="anchor" id="line-443"></span></p></li></ul><p class="line862">}
 4）当前运行进程时间片减为0后的处理方式 struct  task_struct     *task; struct  runqueue   
             *rq; task = current; rq = this_rq; 
if(!--task-&gt;time_slice){ <span class="anchor" id="line-444"></span><span class="anchor" id="line-445"></span></p><ul><li style="list-style-type:none"><p class="line862">if(!TASK_INTERACTIVE(task)||EXPIRED_STARVING(rq)) <span class="anchor" id="line-446"></span></p><ul><li style="list-style-type:none"><p class="line862">enqueue_task(task,rq-&gt;expired); <span class="anchor" id="line-447"></span></p></li></ul>else <span class="anchor" id="line-448"></span><ul><li style="list-style-type:none"><p class="line862">enqueue_task(task,rq-&gt;active); <span class="anchor" id="line-449"></span></p></li></ul></li></ul><p class="line874">} <span class="anchor" id="line-450"></span><span class="anchor" id="line-451"></span></p><p class="line874">对
EXPIRED_STARVING(rq)的解释：宏EXPIRED_STARVING检查运行队列中的第一个过期进程的等待时间是否已经超过1000个
时钟节拍(即1秒)乘以运行队列中的可运行进程数加1，如果是，宏产生值1.如果当前进程的静态优先级大于一个过期进程的静态优先级。该宏也产生值1（参
理解linux内核p273）？？？ <span class="anchor" id="line-452"></span><span class="anchor" id="line-453"></span></p><p class="line867">
</p><h2 id="head-e8f4888ed8544c43fe8596336cd8eb84eaf06c49">O(1)调度器小节</h2>
<span class="anchor" id="line-454"></span><p class="line874">Linux2.6调度器
改进了前任调度器的可扩展性问题，schedule()函数的时间复杂度为O(1)。这取决于两个改进： 一．Pick 
next算法借助于active数组，无需遍历runqueue； 
二．取消了定期更新所有进程counter的操作，动态优先级的修改分布在进程切换，时钟tick中断以及其它一些内核函数中进行。 <span class="anchor" id="line-455"></span><span class="anchor" id="line-456"></span></p><p class="line867">
</p><h2 id="head-05265ed56aed2991e21d7029631866ee06e86917">代码描述</h2>
<span class="anchor" id="line-457"></span><p class="line874">修改文件proc.h、
proc.c、rq.h、rq.c 新增sched_O1.h、sched_O1.c 采用的数据结构： 
为了和算法相结合，我们在proc结构上新增加： int prio; int static_prio; unsigned long 
sleep_avg; 在rq的定义上修改为： struct prio_array { <span class="anchor" id="line-458"></span><span class="anchor" id="line-459"></span></p><ul><li style="list-style-type:none">int proc_num; unsigned long bitmap[BITMAP_SIZE]; struct  rq_node query[MAX_PRIO]; <span class="anchor" id="line-460"></span></li></ul><p class="line874">}; struct rq{ <span class="anchor" id="line-461"></span><span class="anchor" id="line-462"></span></p><ul><li style="list-style-type:none">struct
 spinlock rq_lock; struct prio_array* active; struct prio_array* 
expired; struct prio_array array[2]; int proc_num; int max_slices; 
struct sched_class* sched_class; struct rq* next; struct rq_node* 
free_list; struct sched_class* sub_sched_class; <span class="anchor" id="line-463"></span></li></ul><p class="line874">};
 
在sched_O1.c中定义大量的sched操作函数，除了基本了enqueue、dequeue等操作外，我们还新增加了
set_proc_prio、get_proc_prio、getBitmap、get_first_bitmap、update_prio等函数，实现
的操作是设置优先级、获得优先级、得到相应位信息、获得第一个为1的位。相对于原来的调度看来，需要处理的地方有新的数据结构的适应。 
对实验的后续开发内容建议或设想 后续实验需要完成算法效率的测试代码，更好的和其他调度算法相结合，取得更好的进展。 <span class="anchor" id="line-464"></span><span class="anchor" id="line-465"></span></p><p class="line867">
</p><h2 id="head-557be94e9091139a6e7c472c60877d00a133b793">实验总结</h2>
<span class="anchor" id="line-466"></span><p class="line874">本次实验对于xv6来说就是添加新的算法结构，能够使得xv6正常工作。对于O(1)算法来说，总体觉得在数据结构的运用和设计上，如果有比较新颖的想法，那么得到的结果也将是比较不错的。希望能够更进一步的了解O(1)算法和其他调度算法结合的效果。 <span class="anchor" id="line-467"></span><span class="anchor" id="line-468"></span></p><p class="line867">
</p><h3 id="head-73f1d8f798d96769dc51794fbb43c45f565661c6">20100123-张宇龙提交的O(1)算法代码</h3>
<span class="anchor" id="line-469"></span><ul><li><p class="line891"><a class="attachment" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=get&amp;target=proj_backup.tar.gz" title="attachment:proj_backup.tar.gz">proj_backup.tar.gz</a> <span class="anchor" id="line-470"></span></p></li></ul><p class="line874">向勇的批注：基于该小组的演示报告，目前该版本完成的工作是O(1)算法的基本代码编写，能顺利完成编译，原来的系统可启动；下面需要进行的工作是，编写测试代码，并对代码进行测试和改错。 <span class="anchor" id="line-471"></span><span class="anchor" id="line-472"></span></p><p class="line867">
</p><h2 id="head-30da62ccf277ba12c1f8abd0b21709aed1a7fe53">参考文献</h2>
<span class="anchor" id="line-473"></span><p class="line867"><a class="attachment" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=get&amp;target=LinuxO%281%29%E7%AE%97%E6%B3%95%E5%89%96%E6%9E%90" title="attachment:LinuxO(1)算法剖析">LinuxO(1)算法剖析</a> <span class="anchor" id="line-474"></span><span class="anchor" id="line-475"></span></p><p class="line867"><a class="attachment" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=get&amp;target=Linux%E8%BF%9B%E7%A8%8B%E8%B0%83%E5%BA%A6%E5%88%86%E6%9E%90.pdf" title="attachment:Linux进程调度分析.pdf">Linux进程调度分析.pdf</a> <span class="anchor" id="line-476"></span><span class="anchor" id="line-477"></span></p><p class="line867">
</p><h2 id="head-c474f93037e115b55b4b5656071eb8dcc4e1caca">课堂讨论ppt</h2>
<span class="anchor" id="line-478"></span><p class="line867"><a class="attachment" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile&amp;do=get&amp;target=%E5%A4%84%E7%90%86%E5%99%A8O%281%29%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95.ppt" title="attachment:处理器O(1)调度算法.ppt">处理器O(1)调度算法.ppt</a> <span class="anchor" id="line-479"></span><span class="anchor" id="line-480"></span></p><p class="line867"><span class="anchor" id="line-481"></span></p><pre>助教老师已为你们小组建立了相应的GIT库，请上传你们的代码结果。 git://cherry.cs.tsinghua.edu.cn/xv6-O1  同时，我还注意到你们的Wiki页面上还没有添加任何内容。请及时上传你们的结果。  --向勇  下面是被转发的邮件：  发件人: Jiaqiang Xu &lt;xjqkilling@gmail.com&gt; 日期: 2009年12月29日 下午11时21分09秒 收件人: "向勇 (Yong XIANG)" &lt;xyongcn@gmail.com&gt; 主题: 回复： 建GIT库  已经建好。  向勇 (Yong XIANG) wrote: 徐家强，您好！ 请给做O（1）调度算法的小组建GIT库，然后在下面页面加说明，并在网络学堂中 发公布。谢谢！ --向勇 </pre><span class="anchor" id="line-482"></span><span class="anchor" id="bottom"></span></div><p id="pageinfo" class="info" dir="ltr" lang="en">OsCourseWiki: OsTrain2009/O1  (last edited 2010-12-31 20:14:43 by <span title="wangmeng07 @ 59.66.132.158[59.66.132.158]"><a class="mailto" href="mailto:wbihai@126.com" title="wangmeng07 @ 59.66.132.158[59.66.132.158]">2007011410</a></span>)</p>

<div id="pagebottom"></div>
</div>


<div id="footer">
<ul class="editbar"><li><a name="texteditlink" href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=edit&amp;editor=text">Edit (Text)</a></li><li><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=edit&amp;editor=gui">Edit (GUI)</a></li><li><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=info">Info</a></li><li><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=subscribe">Subscribe</a></li><li><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=quicklink">Add Link</a></li><li><a href="http://os.cs.tsinghua.edu.cn/oscourse/OsTrain2009/O1?action=AttachFile">Attachments</a></li><li>
<form class="actionsmenu" method="get" action="">
<div>
    
    <select name="action" onchange="if ((this.selectedIndex != 0) &amp;&amp;
                      (this.options[this.selectedIndex].disabled == false)) {
                this.form.submit();
            }
            this.selectedIndex = 0;">
        <option selected="selected" value="show">More Actions:</option><option value="raw">Raw Text</option>
<option value="print">Print View</option>
<option value="RenderAsDocbook">Render as Docbook</option>
<option value="refresh">Delete Cache</option>
<option value="show" disabled="disabled" class="disabled">------------</option>
<option value="SpellCheck">Check Spelling</option>
<option value="LikePages">Like Pages</option>
<option value="LocalSiteMap">Local Site Map</option>
<option value="show" disabled="disabled" class="disabled">------------</option>
<option value="RenamePage" disabled="disabled" class="disabled">Rename Page</option>
<option value="DeletePage" disabled="disabled" class="disabled">Delete Page</option>
<option value="show" disabled="disabled" class="disabled">------------</option>
<option value="MyPages">My Pages</option>
<option value="SubscribeUser">Subscribe User</option>
<option value="show" disabled="disabled" class="disabled">------------</option>
<option value="Despam">Remove Spam</option>
<option value="PackagePages">Package Pages</option>
    </select>
    
</div>
<script type="text/javascript">
<!--// Init menu
actionsMenuInit('More Actions:');
//-->
</script>
</form>
</li></ul>

<ul id="credits">
<li><a href="http://moinmoin.wikiwikiweb.de/">MoinMoin Powered</a></li><li><a href="http://www.python.org/">Python Powered</a></li><li><a href="http://validator.w3.org/check?uri=referer">Valid HTML 4.01</a></li>
</ul>


</div>



</body></html>